package com.ljy.my_study.lintcode.线上最多点;

import java.math.BigDecimal;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author James
 * @date 2019年5月6日
 */
public class TestMain {
	// Given n points on a 2D plane, find the maximum number of points that lie on
	// the same straight line.
	// Have you met this question in a real interview? Yes
	// Problem Correction
	// Example
	// Example 1:
	//
	// Input:(1,2),(3,6),(0,0),(1,3).
	// Output:3
	// Example 2:
	//
	// Input:(1,2),(2,3),(3,2).
	// Output:2
	public static void main(String[] args) {
		// k*x+b=y
		// k*x1+b=y1
		// k*x2+b=y2
		// k=(y2-y1)/(x2-x1)
		// b=y1-(y2-y1)/(x2-x1)*x1
		// 在同一点上，另外保存，特别处理
		// 3.0-15.0:
		// [{"x":"0","y":"62"} ,
		// {"x":"272","y":"662"} ,
		// {"x":"-34","y":"-13"} ,
		// {"x":"-340","y":"-688"} ,
		// {"x":"34","y":"137"} ,
		// {"x":"-68","y":"-88"} ,
		// {"x":"-102","y":"-163"} ,
		// {"x":"68","y":"212"} ,
		// {"x":"-68","y":"-88"} ,
		// {"x":"34","y":"137"} ,
		// {"x":"272","y":"662"} ,
		// {"x":"136","y":"362"} ,
		// {"x":"-204","y":"-388"} ,
		// {"x":"-68","y":"-88"} ,
		// {"x":"-204","y":"-388"} ,
		// {"x":"-272","y":"-538"} ,
		// {"x":"238","y":"587"} ,
		// {"x":"34","y":"137"} ,
		// {"x":"170","y":"437"} ,
		// {"x":"170","y":"437"} ]
//		Point[] points = changeStrToPointsArr(
//				"[[29,87],[145,227],[400,84],[800,179],[60,950],[560,122],[-6,5],[-87,-53],[-64,-118],[-204,-388],[720,160],[-232,-228],[-72,-135],[-102,-163],[-68,-88],[-116,-95],[-34,-13],[170,437],[40,103],[0,-38],[-10,-7],[-36,-114],[238,587],[-340,-140],[-7,2],[36,586],[60,950],[-42,-597],[-4,-6],[0,18],[36,586],[18,0],[-720,-182],[240,46],[5,-6],[261,367],[-203,-193],[240,46],[400,84],[72,114],[0,62],[-42,-597],[-170,-76],[-174,-158],[68,212],[-480,-125],[5,-6],[0,-38],[174,262],[34,137],[-232,-187],[-232,-228],[232,332],[-64,-118],[-240,-68],[272,662],[-40,-67],[203,158],[-203,-164],[272,662],[56,137],[4,-1],[-18,-233],[240,46],[-3,2],[640,141],[-480,-125],[-29,17],[-64,-118],[800,179],[-56,-101],[36,586],[-64,-118],[-87,-53],[-29,17],[320,65],[7,5],[40,103],[136,362],[-320,-87],[-5,5],[-340,-688],[-232,-228],[9,1],[-27,-95],[7,-5],[58,122],[48,120],[8,35],[-272,-538],[34,137],[-800,-201],[-68,-88],[29,87],[160,27],[72,171],[261,367],[-56,-101],[-9,-2],[0,52],[-6,-7],[170,437],[-261,-210],[-48,-84],[-63,-171],[-24,-33],[-68,-88],[-204,-388],[40,103],[34,137],[-204,-388],[-400,-106]]"
//						+ "");
		Point[] points = changeStrToPointsArr(
				"[[0,9],[138,429],[115,359],[115,359],[-30,-102],[230,709],[-150,-686],[-135,-613],[-60,-248],[-161,-481],[207,639],[23,79],[-230,-691],[-115,-341],[92,289],[60,336],[-105,-467],[135,701],[-90,-394],[-184,-551],[150,774]]");
//		3.0434782608695654-9.0:
//		[{"x":"0","y":"9"} , 
//		 {"x":"115","y":"359"} , 
//		 {"x":"115","y":"359"} , 
//		 {"x":"-161","y":"-481"} , 
//		 {"x":"207","y":"639"} , 
//		 {"x":"-230","y":"-691"} , 
//		 {"x":"23","y":"79"} , 
//		 {"x":"-115","y":"-341"} , 
//		 {"x":"138","y":"429"} , 
//		 {"x":"230","y":"709"} , 
//		 {"x":"92","y":"289"} , 
//		 {"x":"-184","y":"-551"} ]
		System.out.println(maxPoints(points));
	}

	public static int maxPoints(Point[] points) {
		if (points == null)
			return 0;
		if (points.length <= 2)
			return points.length;
		Map<String, Set<Point>> map = new HashMap<>();
		int len = points.length;
		int max = 0;
		for (int i = 0; i < len - 1; i++) {
			int samePointsCount=0;
			Set<Point> set=new HashSet<>();
			for (int j = i + 1; j < len; j++) {
				int x = points[i].x - points[j].x;
				int y = points[i].y - points[j].y;
				if (x == 0) {
					setPoints(map, "special" + "-" + points[i].x, points[i], points[j]);
					max = Math.max(max, map.get("special" + "-" + points[i].x).size());
					if(y==0&&x==0) {
//						samePointsCount++;
						set.add(points[i]);
						set.add(points[j]);
					}
					continue;
				}
				BigDecimal bd1 = new BigDecimal(y);
//				double k = bd1.divide(new BigDecimal(x), 3, BigDecimal.ROUND_HALF_UP).doubleValue();
				double k=y/(double)x;
				double b = points[i].y - k * points[i].x;
				String key = "" + k + "-" + b;
				setPoints(map, key, points[i], points[j]);
//				max = Math.max(max, map.get(key).size()+samePointsCount);
				if(max==13) {
					System.out.println(key+":"+map.get(key));
				}
			}
		}
		System.out.println(map);
		return max;
	}

	public static void setPoints(Map<String, Set<Point>> map, String key, Point... points) {
		if (map.get(key) == null) {
			map.put(key, new HashSet<>());
		}
		for (Point p : points) {
			map.get(key).add(p);
		}
		if (map.get(key).size() == 13)
			System.out.println(key + ":" + map.get(key));
	}

	// public static int maxPoints(Point[] points) {
	// if (points.length == 0 || points == null)
	// return 0;
	//
	// if (points.length == 1)
	// return 1;
	//
	// int max = 1; // the final max value, at least one
	// for (int i = 0; i < points.length; i++) {
	// HashMap<Float, Integer> hm = new HashMap<Float, Integer>();
	// int same = 0;
	// int localmax = 1; // the max value of current slope, at least one
	// for (int j = 0; j < points.length; j++) {
	// if (i == j)
	// continue;
	//
	// if (points[i].x == points[j].x && points[i].y == points[j].y) {
	// same++;
	// continue;
	// }
	//
	// float slope = ((float) (points[i].y - points[j].y)) / (points[i].x -
	// points[j].x);
	//
	// if (hm.containsKey(slope))
	// hm.put(slope, hm.get(slope) + 1);
	// else
	// hm.put(slope, 2); // two points form a line
	// }
	//
	// for (Integer value : hm.values())
	// localmax = Math.max(localmax, value);
	//
	// localmax += same;
	// max = Math.max(max, localmax);
	// }
	// return max;
	// }

	// public static int maxPoints(Point[] points) {
	// if(points==null||points.length==0) {
	// return 0;
	// }
	// if(points.length==1) {
	// return 1;
	// }
	// int max=0;
	// Map<Double,Integer> map=new HashMap<>();
	// for(int i=0;i<points.length-1;i++) {
	// for(int j=i+1;j<points.length;j++) {
	//
	// }
	// }
	// return 0;
	// }

	public static Point[] changeStrToPointsArr(String pointsStr) {
		int strLen = pointsStr.length();
		String[] pointsStrArr = pointsStr.substring(2, strLen - 2).split("\\]" + "," + "\\[");
		Point[] points = new Point[pointsStrArr.length];
		for (int i = 0; i < points.length; i++) {
			Point p = new Point();
			String[] strArr = pointsStrArr[i].split(",");
			p.x = Integer.valueOf(strArr[0]);
			p.y = Integer.valueOf(strArr[1]);
			points[i] = p;
		}
		return points;
	}

	public static class Point {
		int x;
		int y;

		Point() {
			x = 0;
			y = 0;
		}

		Point(int a, int b) {
			x = a;
			y = b;
		}

		@Override
		public String toString() {
			return "{\"x\":\"" + x + "\",\"y\":\"" + y + "\"} ";
		}

	}

}
